package suanfa;

public class InsertSortTest {
    public static void main(String[] args) {
        int[] arr = new int[]{5, 3, 4, 2, 1, 2, 3, 4};
        sortByInsert(arr);
        print(arr);
    }

    private static void print(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }

    private static void sortByInsert(int[] arr) {
        int N = arr.length;
        //让0-end 有序
        for (int end = 1; end < N; end++) {
            let0ToEndSort(arr, end);
            //System.out.println("0到" + end + "有序");
        }
    }

    private static void let0ToEndSort(int[] arr, int end) {
         /*
         //第一版
         for (int i = end; i > 0; i--) {
            if (arr[i] < arr[i - 1]) {
                int tmpVal = arr[i];
                arr[i] = arr[i - 1];
                arr[i - 1] = tmpVal;
            } else {
                break;
            }
        }*/
        //第二版
        while (end > 0 && arr[end] < arr[end - 1]) {
            int tmpVal = arr[end];
            arr[end] = arr[end - 1];
            arr[end - 1] = tmpVal;
            end--;
        }
    }
}
